// 思路：1. 首先确定桶的大小，然后根据数据的大小区间确定越到桶的数量
// 2. 将元素分配到不同的桶中，对每个桶进行插入排序
// 3. 合并桶内的数据
// 时间复杂度：最坏On2，最好On+k，k为桶的个数，如果桶内插入排序，平均为On+k
// 空间复杂度：On+k，k为桶的个数
// 稳定性：稳定排序算法
// 适用场景：适用于待排序元素的值域范围较大，且桶的个数较少的情况

function bucketSort(arr, bucketSize = 5) {
    let maxVal = Math.max(...arr)
    let minVal = Math.min(...arr)
    let len = Math.ceil((maxVal - minVal) / bucketSize)
    let bucketArr = new Array(len).fill(0).map(() => [])
    for (let i = 0; i < arr.length; i++) {
        bucketArr[Math.floor((arr[i] - minVal) / bucketSize)].push(arr[i])
    }
    let result = []
    for (let i = 0; i < bucketArr.length; i++) {
        insertSort(bucketArr[i])
        result.push(...bucketArr[i])
    }
    return result
}

function insertSort(arr) {
    for (let i = 1; i < arr.length; i++) {
        let j = i
        // 先记录下temp数据，然后一个个比较，把大于temp的往后退一位
        let temp = arr[i]
        while (j > 0 && arr[j - 1] > temp) {
            arr[j] = arr[j-1]
            j--
        }  
        arr[j] = temp
    }
}

let arr = [2, 7, 26, 25, 19, 17, 1, 90, 3, 36]
console.log(bucketSort(arr));